package vip.zhenzicheng.algorithm.leetcode.str;

/**
 * <a href="https://leetcode.cn/problems/longest-palindromic-substring/">最长回文子串 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-07-19 15:22
 */
public class LongestPalindromicSubstring_5 {

  public String longestPalindrome(String s) {
    int len = s.length();
    int maxStart = 0, maxEnd = 0;

    for (int i = 0; i < len; i++) {
      // 以当前字符为中心左右遍历，例如："aba"，i=1
      int charCenterLen = expandAroundCenter(s, i, i, len);
      // 以空白字符为中心，例如："abba"，i=1
      int blackCenterLen = expandAroundCenter(s, i, i + 1, len);
      int maxLen = Math.max(charCenterLen, blackCenterLen);

      if (maxLen > (maxEnd - maxStart)) {
        maxStart = i - (maxLen - 1) / 2;
        maxEnd = i + maxLen / 2;
      }
    }
    return s.substring(maxStart, maxEnd + 1);
  }

  // 从给定左右位置在字符串中寻找回文子串
  private int expandAroundCenter(String s, int l, int r, int len) {
    while (l >= 0 && r < len && s.charAt(l) == s.charAt(r)) {
      l--;
      r++;
    }
    return r - l - 1;
  }
}
